package _04_队列;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class _239_滑动窗口最大值 {

    // nums = [1,3,-1,-3,5,3,6,7], k = 3
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        _239_滑动窗口最大值 v = new _239_滑动窗口最大值();
        int[] ints = v.maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(ints));
    }

    // 双端队列解法
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (k == 1) return nums;
        int[] max = new int[nums.length - k + 1];
        // 维护一个双端队列
        Deque<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            int j = i - k + 1;
            while (!list.isEmpty() && nums[list.peekLast()] < nums[i]) {
                // 弹出队尾元素
                list.pollLast();
            }
            // 直接添加
            list.offerLast(i);
            if (j >= 0) {
                if (list.peekFirst() < j) {
                    // 不在元素内
                    list.pollFirst();
                }
                max[j] = nums[list.peekFirst()];
            }
        }
        return max;
    }

    // 顺推法
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k <= 1) return nums;
        int[] maxs = new int[nums.length - k + 1];
        int maxIndex = 0;
        // 求出前k项最大元素的索引值
        for (int i = 1; i < k; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        for (int begin = 0; begin < maxs.length; begin++) {
            int end = begin + k - 1;
            if (nums[end] > nums[maxIndex]) {
                // 更新最大索引
                maxIndex = end;
            } else if (maxIndex < begin) {
                maxIndex = begin;
                // 最大索引范围不在滑动窗口内
                for (int i = begin + 1; i <= end; i++) {
                    if (nums[i] > nums[maxIndex]) {
                        maxIndex = i;
                    }
                }
            }
            maxs[begin] = nums[maxIndex];
        }
        return maxs;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length <= 1) return nums;
        // 滑动窗口存储元素的最大值
        int[] ints = new int[nums.length - k + 1];
        // 寻找出第一个滑动窗口的最值的索引
        int max = 0;
        for (int i = 1; i < k; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        // 第一个滑动窗口元素
        ints[0] = nums[max];
        for (int i = k; i < nums.length; i++) {
            // 当前弹出的索引
            int popIndex = i - k;
            int mapResultIndex = popIndex + 1;
            // 移入滑动窗口的元素
            if (nums[i] > nums[max]) {
                ints[mapResultIndex] = nums[i];
                max = i;
            } else {
                // 不大于
                if (popIndex >= max) {
                    max = popIndex + 1;
                    // 重新计算滑动窗口最大值
                    for (int j = popIndex + 2; j <= i; j++) {
                        if (nums[j] > nums[max]) {
                            max = j;
                        }
                    }
                }
                ints[mapResultIndex] = nums[max];
            }
        }
        return ints;
    }

}
